package com.ruijixiang.leetcode.everyday.leetcode2024.leetcode202409;

import java.lang.reflect.Array;
import java.util.*;

public class leetcode20240917 {
    public int numBusesToDestination(int[][] routes, int source, int target){
        Map<Integer, List<Integer>> stopToBuses=new HashMap<>();// 换成map
        for(int i=0;i<routes.length;i++){
            for(int x : routes[i]){
                stopToBuses.computeIfAbsent(x,k->new ArrayList<>()).add(i);// 经过车站x的有公交车i
            }
        }

        if(!stopToBuses.containsKey(source) || !stopToBuses.containsKey(target)){
            return source==target ? 0 : -1;
        }

        // BFS
        Map<Integer,Integer> dis=new HashMap<>(); // source->target的换乘次数
        dis.put(source,0);
        Queue<Integer> q=new ArrayDeque<>();
        q.add(source);
        while(!q.isEmpty()){
            int x=q.poll();// 当前在车站x
            int disX=dis.get(x);// 到达车站x已经换乘的次数
            for(int i : stopToBuses.get(x)){// 经过车站x的公交车编号有哪些
                if(routes[i]!=null){
                    for(int y : routes[i]){ // 遍历公交车i经过哪些站点
                        if(!dis.containsKey(y)){
                            dis.put(y,disX+1);
                            q.add(y);
                        }
                    }
                    routes[i]=null;
                }
            }
        }
        return dis.getOrDefault(target,-1);
    }
}
